1. Field of the Invention
This invention relates generally to a method for layout compaction to be performed in a system for generating a layout pattern (hereunder sometimes referred to simply as a layout) of an integrated circuit (IC) such as a very-large-scale integrated circuit (VLSI) and more particularly to a method for VLSI layout pattern compaction for reducing manufacturing costs of ICs such as VLSIs by obtaining a layout which meets a design rule and minimizes an area occupied by an IC.
2. Description of the Related Art
Recent advances in IC fabrication techniques promote refinement of design rules for determining, for example, a minimum distance between adjacent metal lines. To manufacture chips more inexpensively, there is necessity of effective utilization of a conventional resource of a layout. Moreover, there is also necessity of reducing unnecessary spaces which are generally caused in the process of implementing a layout. Therefore, a technique of an automatic conversion of a conventional design rule previously designed into a new one, as well as a compaction technique by which a layout consistent with a design rule can be obtained and unnecessary spaces are decreased in such a layout, is indispensable.
There has been proposed a typical example of conventional practical compaction techniques which is based on a plane sweep method known in the field of computational geometry. For example, compaction techniques employing an enhanced plane sweep method are disclosed in an article entitled "High-Speed Multi-Function Channel Spacer with Deletion of Vias", Denshi-Joho-Tsushin-Gakkai Ronbun-Shi A, Vol. J72-A No. 2, February 1989, pp. 349-358 and an article entitled "Nutcracker: An Efficient and Intelligent Channel Spacer", Proc. of the 24th Design Automation Conference, June 1989, pp. 298-304.
The plane sweep method has the following advantages:
(1) This method is by sufficiently flexible to be able to easily follow complex design rules because wires, contacts and so on are dealt with by processing graphic information representing them and the compact is effected by performing a simple processing.
(2) This method can easily deal with a bending of a wire.
(3) This method is effective in producing a layout of irregular geometry.
The plane sweep method is a technique by which a horizontal line (hereunder referred to as a scan line) is assumed in a plane and geometrical data representing graphic forms such as a line segment intersecting the scanning line is searched moving the scan line from bottom to top (or from top to bottom) in the plane. Such a plane sweep operation usually consists of two phases, namely, a first and second phases. In the first phase, an arrangement of the geometrical data is effected by arranging top and bottom endpoints in the ascending order of size, and ordinates (i.e., y-coordinates) of the arranged endpoints are held in a list "y-queue". Further, in the second phase, the following operation is repeated. Namely, the ordinates of the endpoints held in the list named "y-queue" are read therefrom one by one. Then the read ordinate is inserted into a work list named "x-table" if the corresponding endpoint is a bottom one. In contrast, the read ordinate is deleted from the list "y-queue" if the corresponding endpoint is a top one. Thereby, the geometrical data representing graphic forms intersecting the scanning line are always held in the work list "x-table". Let n be the number of data (thus, be a positive integer). The operation of the first phase can be performed in time O(nlogn). If balanced binary trees using abscissas (i.e., x-coordinates) as keys are employed as a data structure of the work list "x-table", each of the insertion and deletion operations of the second phase can be done within time bound O(nlogn). Thus the entire plane sweep operation can be accomplished in time O(nlogn). Consequently, time complexity of the plane sweep method is O(nlogn).
Despite the above described advantages, the plane sweep technique is inefficient because of the fact that when the number n of data to be processed increases, a processing time also increases in proportion to nlogn. Moreover, in case of employing the plane sweep method, it is difficult to employ a multiprocessing system using a plurality of processors for processing data at a high speed. The present invention is created to resolve the above stated problems of the conventional compaction technique based on the plane sweep method.
It is accordingly an object of the present invention to provide a method for layout compaction which has the advantages of the plane sweep method and can perform a packing-element-in-bottom-boundary-region or squeeze-down processing and a packing-element-in-top-boundary-region or lift-up processing, which will be described later, at a high speed.
It is another object of the present invention to provide a method for layout compaction in which even if the number n (n is a positive integer) of data increases, an increase in processing time can be restrained to an extent proportional to the number n of data.
It is still another object of the present invention to provide a high-speed method for layout compaction which can perform a multiprocessing at a high speed.